\chapter{Стандартная библиотека}

\section{Лекция 13.03.2012. Алгоритмы}

\subsection{Миниалгоритмы}

Смешно, но swap это стандартный алгоритм stl, его можно специализировать для своего класса. Обычно swap выглядит следующим образом:
\begin{lstlisting}
void swap(T &a, T &b)
{
	T t(a);
	a = b;
	b = t;
}
\end{lstlisting}

но в некоторых случаях возможна и более умная реализация.

Аналог swap, но работающий через итераторы это iter\_swap.

Два совсем простых алгоритма max и min, которые существуют в двух версиях: с двумя параметрами и с тремя параметрами, где третий параметр, очевидно, компаратор.

Компаратор - функтор, т. е. некоторая сущеность f, которая может вызываться следующим образом f(T, T).

\subsection{Алгоритмы не модифицирующие последовательность}

count и count\_if - считают сколько раз встречаются элемент (или элементы) последовательности:
\begin{lstlisting}
size_t count(FwdIt p, FwdIt q, T const& v);
size_t count_if(FwdIt p, FwdIt q, Pred pred);
\end{lstlisting}

equal и lexicographical\_compare позволяют сравнивать последовательности.

Еще один частый алгоритм find (find\_if):
\begin{lstlisting}
It find(It, It, val);
It find\_if(It, It, Pred);
\end{lstlisting}

Видно, что сигнатуры всех таких методов похожи. Еще одно важное замечание, если find не находит, что-то то возвращается второй итератор.

Из алгоритмов поиска есть еще find\_first_of, который принимает уже четыре итератора, два на одну последовательность и два на вторую.

Кроме того существует популярный алгоритм for\_each, который на самом деле может изменять элементы последовательности:
\begin{lstlisting}
for_each(It, It, F);
\end{lstlisting}
который для каждого элемента подпоследовательности вызывает передаваемый функтор.

\subsection{Алгоритмы требущие отсортированных последовательностей}

binary\_search - этот алгоритм просто проверяет наличие алгоритма в контейнере, и возвращает не итератор, а bool, для поиска элемента для дальнейшего
использования следуют обратить внимание на следующие алгоритмы.

lower\_bound, upper\_bound и equal\_range - ищут нижнюю, верхнюю или обе границы для вставки.

\subsection{Модифицирующие алгоритмы}

Есть набор алгоритмов для заполнения последовательности: fill и fill\_n (принимает, количество элементов), generate и generate\_n (отличаются от fill, тем что
принимает функтор без параметров)

Кроме того существует алгоритм для перемешивания последовательности random\_shuffle.

copy и copy\_backwards копирут последовательности определеяемые двумя итераторами в место, указанное output итератором.

remove\_copy - скопировать последовательность выкинув из нее некоторые значения, и remove\_copy\_if - копирование по предикату.

Замена осуществляется целым набором функций replace, replace\_copy, replace\_copy\_if и replace\_if.

reverse, reverse\_copy - очевидно, что они делают из названия.

rotate и rotate\_copy - циклический сдвиг.

remove и remove\_if - удаляют элементы

unique и unique\_copy - удаляют одинаковые !!!рядом стоящие!!! элементы из последовательности.

\paragraph{Примечания об удалении} на самом деле функции удаления из контейнера ничего из него не удаляют, они перемещают на место удаляемых элементов следующие
по порядку элементов, и в конце возвращают итератор на место, где последовательность должна была бы закончится после удаления. И это друья мои пипец...

\paragraph{Как правильно пользоваться всем этим страхом}:
\begin{lstlisting}
std::vector<...> v;
...
v.erase( remove( v.begin(), v.end() ), v.end() );
...
v.erase( unique( v.begin(), v.end() ), v.end() );
\end{lstlisting}

Еще один полезный алгоритм transform, который применяет к каждому элементу последовательности функтор и создает из этого новую последовательность.
Существует transform для двух последовательностей и соответствующим функтором. Вместе с transform полезно посмотреть еще и на accumulate.

\subsection{Сортировки и прочее}

sort и stable\_sort - сортировки, требуют RandomAccessIterator

nth\_element - порядковая статистика

partition - разделение (как в quick sort)

partition\_sort - частичная сортировка

merge - слить две последовательности по порядку